package trap

// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//动态规划，leftMax和rightMax分别记录下标i处，左右两边的最高值
// 下标i处的积水量为 leftMax、rightMax中最小的值减去height[i]
func trap(height []int) int {
	max := height[0]
	n := len(height)
	for i := 1; i < len(height); i++ {
		if max < height[i] {
			max = height[i]
		}
	}

	count := 0
	leftMax := make([]int, n)
	leftMax[0] = height[0]
	for i := 1; i < len(height); i++ {
		leftMax[i] = maxHeight(leftMax[i-1], height[i])
	}

	rightMax := make([]int, n)
	rightMax[n-1] = height[n-1]
	for i := n - 2; i > -1; i-- {
		rightMax[i] = maxHeight(height[i], rightMax[i+1])
	}

	for index := 0; index < n; index++ {
		count += minHeight(leftMax[index], rightMax[index]) - height[index]
	}
	return count
}

// 左右两个链表往中间靠
// 每次更新leftMax、rightMax为历史最大值
// 如果height[left] < height[right] 则leftMax < rightMax
// 积水量为leftMax - height[left]
func trap2(height []int) int {
	n := len(height)
	left, right := 0, n-1
	leftMax, rightMax := 0, 0
	count := 0
	for left < right {
		leftMax = maxHeight(leftMax, height[left])
		rightMax = maxHeight(rightMax, height[right])

		if height[left] < height[right] {
			count += leftMax - height[left]
			left++
		} else {
			count += rightMax - height[right]
			right--
		}
	}
	return count
}

// 找出最高点
// 从两边开始往中间靠，下一个比当前值小说明可以积水
// 注意比较的当前值要及时更新为历史最大值
func trap3(height []int) int {
	max := 0
	n := len(height)
	for i := 1; i < len(height); i++ {
		if height[max] < height[i] {
			max = i
		}
	}
	i, j := 0, n-1
	count := 0
	temp := height[0]
	for i < max {
		if height[i+1] < temp {
			count += temp - height[i+1]
		} else {
			temp = height[i+1]
		}

		i++

	}
	temp = height[n-1]
	for j > max {
		if height[j-1] < temp {
			count += temp - height[j-1]
		} else {
			temp = height[j-1]
		}
		j--
	}
	return count
}

func maxHeight(i, j int) int {
	if i > j {
		return i
	}
	return j
}

func minHeight(i, j int) int {
	if i < j {
		return i
	}
	return j
}
